package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=13&tqId=1374963&ru=%2Fpractice%2F435fb86331474282a3499955f0a41e8b&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=">二叉树的镜像</a>
 * <p>操作给定的二叉树，将其变换为源二叉树的镜像。</p>
 * <p>数据范围：二叉树的节点数0≤n≤1000 ， 二叉树每个节点的值0≤val≤1000</p>
 * <p>要求：空间复杂度O(n) 。本题也有原地操作，即空间复杂度O(1) 的解法，时间复杂度O(n)
 * <pre>
 * 例如输入：
 *
 *      4
 *
 *    /   \
 *
 *   2     7
 *
 *  / \   / \
 *
 * 1   3 6   9
 *
 *
 * 镜像输出：
 *
 *      4
 *
 *    /   \
 *
 *   7     2
 *
 *  / \   / \
 *
 * 9   6 3   1
 * </pre>
 *
 * @author c2b
 * @since 2023/3/9 11:36
 */
public class JzOffer0027Mirror_S {

    public TreeNode Mirror(TreeNode pRoot) {
        if (pRoot == null) {
            return null;
        }
        // 创建队列并将根节点加入到队列中
        final Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        // 队列中元素不为空
        while (!queue.isEmpty()) {
            // 弹出节点。将左右子节点分别入队，用于记录哪些节点的左右子节点需要镜像交换
            final TreeNode currNode = queue.poll();
            if (currNode.left != null) {
                queue.offer(currNode.left);
            }
            if (currNode.right != null) {
                queue.offer(currNode.right);
            }
            // 交换左右子节点
            final TreeNode temp = currNode.left;
            currNode.left = currNode.right;
            currNode.right = temp;
        }
        return pRoot;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(9);
        root.right.right = null;
        JzOffer0027Mirror_S jzOffer0027Mirror = new JzOffer0027Mirror_S();
        TreeNode mirror = jzOffer0027Mirror.Mirror(root);
        System.out.println();
    }

}
